package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/27 11:25
 */
public class 不同骰子序列的数目 {
    //https://leetcode.cn/problems/number-of-distinct-roll-sequences/
    static int mod = (int) (1e9 + 7);
    static int N = (int) 1e4;
    static int[][][] dp = new int[N + 1][8][8];

    public int distinctSequences(int n) {
        return dfs(n, 7, 7);
    }

    public int dfs(int i, int j, int k) {
        if (i == 0)
            return 1;
        if (dp[i][j][k] != 0)
            return dp[i][j][k];

        int res = 0;
        for (int x = 1; x <= 6; x++) {
            if (x == j || x == k || gcd(x, j) != 1)
                continue;
            res = (res + dfs(i - 1, x, j)) % mod;
        }
        return dp[i][j][k] = res;
    }


    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        不同骰子序列的数目 s = new 不同骰子序列的数目();
        System.out.println();
    }
}
